package leetcode.templates.trees;

public class NumArray {

	int N;
	int[] array;
	int[] sum;
	Integer[] update;

	public NumArray(int[] nums) {
		this.N = nums.length;
		this.array = new int[N + 1];
		for (int i = 0; i < nums.length; i++) {
			array[i + 1] = nums[i];
		}
		this.sum = new int[N << 2];
		this.update = new Integer[N << 2];//
		this.build(1, N, 1);
	}

	private void build(int l, int r, int root) {
		if (l == r) {
			sum[root] = this.array[l];
			return;
		}
		int mid = (l + r) >> 1;
		this.build(l, mid, root << 1);//
		this.build(mid + 1, r, (root << 1) | 1);
		this.sum(root);
	}

	private void sum(int root) {
		sum[root] = sum[root << 1] + sum[(root << 1) | 1];
	}

	public void update(int index, int val) {
		this.update(index + 1, index + 1, val, 1, N, 1);
	}

	public int sumRange(int left, int right) {
		return this.query(left + 1, right + 1, 1, N, 1);
	}

	private void update(int left, int right, int val, int l, int r, int root) {
		if (left <= l && r <= right) {
			this.update[root] = val;
			this.sum[root] = val * (r - l + 1);
			return;
		}
		int mid = (l + r) >> 1;
		push(root, mid - l + 1, r - mid);
		if (left <= mid) {
			this.update(left, right, val, l, mid, root << 1);
		}
		if (right > mid) {
			this.update(left, right, val, mid + 1, r, (root << 1) | 1);
		}
		this.sum(root);
	}

	private int query(int left, int right, int l, int r, int root) {
		if (left <= l && r <= right) {
			return this.sum[root];
		}
		int mid = (l + r) >> 1;
		push(root, mid - l + 1, r - mid);
		int sumLeft = 0;
		if (left <= mid) {
			sumLeft = this.query(left, right, l, mid, root << 1);
		}
		int sumRight = 0;
		if (right > mid) {
			sumRight = this.query(left, right, mid + 1, r, (root << 1) | 1);
		}
		return sumLeft + sumRight;
	}

	private void push(int root, int ln, int rn) {
		if (this.update[root] != null) {
			int update = this.update[root];
			this.update[root << 1] = update;
			this.update[(root << 1) | 1] = update;
			this.sum[root << 1] = update * ln;
			this.sum[(root << 1) | 1] = update * rn;
			this.update[root] = null;
		}
	}
}
